#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include "../base/KMP.c"

#define StringLength 1000000
#define PatternLength 100000

int main() {
    char* string = malloc(sizeof(char)*StringLength);
    char* pattern = malloc(sizeof(char)*PatternLength);

    scanf("%s", string);
    int n;
    scanf("%d", &n);
    for (int i=0; i < n; i++) {
        scanf("%s", pattern);
        Position p = KMP(string, pattern);
        if (p == NotFound) {
            printf("Not Found\n");
        } else {
            printf("%s\n", string + p);
        }
    }
    free(pattern);
    free(string);
    return 0;
}
